package com.data_structure_algorithm.sort;

import java.util.Arrays;

/**
 * @Authror PABLO
 * @Date 2022/3/30 21:47
 * @Desc 堆排序
 */
public class HeapSort {
    static int[] arr = {4, 6, 8, 5, 9, -1, 90, 89, 56, -999};


    public static void main(String[] args) {
        isHeapSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void isHeapSort2(int[] arr) {

        //排序
        //步骤：  建立堆
        buildHeap2(arr);

        //将顶堆值和末尾值交换
        for (int i = arr.length - 1; i >=0 ; i--) {

            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            convert2(arr,0,i-1);
        }

    }

    private static void buildHeap2(int[] arr) {
        //创建堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {

            convert2(arr, i, arr.length - 1);
        }

    }


    public static void convert2(int[] arr, int index, int len) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;

        //临时做引 保存最大值
        int tempIndex = 0;

        if (left <= len && right <= len) {
            tempIndex = arr[left] > arr[right] ? left : right;
        } else if (left <= len) tempIndex = left;
        else if (right <= len) tempIndex = right;
            //递归退出条件
        else return;


        //如果当前最大值比index大
        if (arr[tempIndex] > arr[index]) {
            //交换位置，继续下沉比较
            int temp = arr[tempIndex];
            arr[tempIndex] = arr[index];
            arr[index] = temp;

            convert2(arr, tempIndex, len);
        }

    }


    private static void isHeapSort(int[] arr) {

        buildHeap(arr);

        //交换首尾数据
        for (int i = arr.length - 1; i >= 1; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            convert(arr, 0, i - 1);
        }

    }

    private static void buildHeap(int[] arr) {

        //构建堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) { //下沉操作
            convert(arr, i, arr.length - 1);

        }

    }


    public static void convert(int[] arr, int index, int len) {

        int left = index * 2 + 1;
        int right = index * 2 + 2;

        int tempIndex = 0;


        if (left <= len && right <= len) tempIndex = arr[left] > arr[right] ? left : right; //获取较大值
        else if (left <= len) tempIndex = left;//在下沉过程中，不断获取左右索引，可能会越界，因为是递归调用
        else if (right <= len) tempIndex = right;
        else return;//这里提供下标越界的结束条件，不满足上面三个，说明越界了，即结束

        //和当前比较
        if (arr[index] < arr[tempIndex]) {
            int temp = arr[index];
            arr[index] = arr[tempIndex];
            arr[tempIndex] = temp;
            //递归下沉
            convert(arr, tempIndex, len);
        }
    }

}
